[洛谷P1445][Violet]樱花

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

求方程
$$ \frac{1}{X}+\frac{1}{Y}=\frac{1}{N!} $$
的正整数解的组数，其中N≤10^6。
解的组数，应模1e9+7。

输入格式

输入一个整数N

输出格式

输出答案

题解

部分内容参考自这篇文章

$$ \frac{1}{x}+\frac{1}{y}=\frac{1}{n!} $$

先通分

$$ \frac{(x+y)}{xy}=\frac{1}{n!} $$

再化整数

$$ xy-(x+y)*n!=0 $$

然后配平

$$ (n!)^2-(x+y)*n!+xy=(n!)^2 $$

最后

$$ (x-n!)*(y-n!)=(n!)^2 $$

然后我们发现$x，y$都要是正整数；

所以原题可以变为

$$ A*B=(n!)^2 $$

当$A*B$为正整数的时候$x,y$显然也是正整数；
$x,y$可以是任意正整数，即$A,B$可以为任意正整数，我们就可以对$x$单独进行讨论
我们考虑$x$的取值，显然，若一个质数$p$有$k$个，那么$x$可以取$p^0,p^1….p^k$ 共$(k+1)$种情况
乘法原理乘起来就可以了,而且显然，x确定后，y必然也会被确定
那么我们先可以筛出质数（这里是埃氏筛法）；
求出每个数的最小质因数然后暴力就好了；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1000005;
const int mod=1e9+7;
int n;
long long v[MAXN],phi[MAXN],p[MAXN],cnt;
int c[MAXN];

int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
        if(v[i])continue;
        p[++cnt]=i;
        for(int j=1;j*i<=n;j++)v[i*j]=1;
    }
	long long k=0,ans=1;
    for(int i=1;i<=cnt;i++){
        int pri=p[i],c1=0;
        for(int j=n;j;j/=pri){
            c1+=j/pri;
        }
        c[++k]=c1;
    }
	for(int i=1;i<=cnt;i++)ans=ans*(c[i]*2+1)%mod;
	cout<<ans;
	return 0;
}